package prepare;

import java.util.HashMap;
import java.util.Map;

/**
 * ImplementsLRU 使用缓存  + 双向链表实现 LRU缓存
 *
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: LRU
 * @date 2023/2/21
 **/
public class ImplementsLRU {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 1);
        lruCache.put(2, 2);
        lruCache.put(3, 3);
        System.out.println(lruCache.get(1));
//        Map<String, String> map  = new HashMap<>();
//        map.put("a", "a");
//        System.out.println(map.size());
//        map.remove("a");
//        System.out.println(map.size());
    }

    static class LRUCache {

        /**
         * 缓存值，便于进行访问
         */
        private Map<Integer, DLinkNode> cache;

        /**
         * 容量
         */
        private Integer capacity;

        /**
         * 头节点
         */
        private DLinkNode head;

        /**
         * 尾部节点
         */
        private DLinkNode tail;

        /**
         * 节点值
         */
        class DLinkNode {

            /**
             * 提供访问的 Key
             */
            private int key;

            /**
             * 节点值
             */
            private int value;

            /**
             * 上一个元素
             */
            private DLinkNode prev;

            /**
             * 下一个元素
             */
            private DLinkNode next;
        }

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.cache = new HashMap();
            head = new DLinkNode();
            tail = new DLinkNode();
            head.next = tail;
            tail.prev = head;
        }


        public int get(int key) {
            DLinkNode node = cache.get(key);
            if (node == null) {
                return -1;
            }
            // 将访问的节点移动至头部
            moveToHeadWithValueChange(node, null);
            return node.value;
        }

        public void put(int key, int value) {

            if (cache.get(key) != null) {
                DLinkNode node = cache.get(key);
                moveToHeadWithValueChange(node, value);
                node.value = value;
                cache.put(key, node);
                return;
            }

            // 容量满 需要进行淘汰
            if (cache.size() == capacity) {
                removeTail();
            }

            DLinkNode newNode = addToHead(key, value);
            cache.put(key, newNode);
        }


        /**
         * 将节点移动至 head 可改动值
         *
         * @param key
         * @param value
         */
        private DLinkNode moveToHeadWithValueChange(DLinkNode node, Integer value) {
            if (value != null) {
                node.value = value;
            }

            // cur 从之前的位置清除
            node.next.prev = node.prev;
            node.prev.next = node.next;

            // 将 cur 移动到头部
            node.next = head.next;
            head.next.prev = node;

            // 让 head 指针指向 cur
            head.next = node;
            node.prev = head;

            return node;
        }

        /**
         * 将节点移动至 head
         *
         * @param key
         * @param value
         */
        private DLinkNode addToHead(int key, Integer value) {
            DLinkNode cur = new DLinkNode();
            cur.key = key;
            cur.value = value;

            // 将 cur 移动到头部
            cur.next = head.next;
            head.next.prev = cur;

            // 让 head 指针指向 cur
            head.next = cur;
            cur.prev = head;

            return cur;
        }

        /**
         * 删除尾节点值
         *
         * @param key
         * @param value
         */
        private void removeTail() {
            DLinkNode last = tail.prev;
            last.prev.next = tail;
            tail.prev = last.prev;

            // 删除缓存值
            cache.remove(last.key);
        }
    }
}



